package com.leetcode;

import com.leetcode.support.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 437 路径总和 (三)
 *
 * @author yml
 * 给定一个二叉树的根节点 root，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 */
public class LeetCode437 {

    public static void main(String[] arg0) {
        Object[] nums = {10, 5, -3, 3, 2, null, 11, 3, -2, null, 1};
        System.out.println("路径总和 = " + pathSum(new TreeNode(nums), 8));
    }

    public static int pathSum(TreeNode root, int targetSum) {
        Map<Integer, Integer> counts = new HashMap<>();
        // 这里设置0对应的值为1，这样如果第一个根节点就等于目标和，在递归中给res赋的值就是1，不需要再判断
        counts.put(0, 1);
        return childMethod(root, counts, 0, targetSum);
    }

    /**
     * 递归 + 前缀和
     */
    public static int childMethod(TreeNode node, Map<Integer, Integer> counts, int currSum, int targetSum) {
        if (node == null || !node.isValidVal()) { // 递归到了最末端终止，并且返回0条符合条件路径
            return 0;
        }

        int res = 0;

        currSum += node.val;
        res = counts.getOrDefault(currSum - targetSum, 0); // 这里赋值不明白

        counts.put(currSum, counts.getOrDefault(currSum, 0) + 1); // 记录前缀和的次数
        res += childMethod(node.left, counts, currSum, targetSum);
        res += childMethod(node.right, counts, currSum, targetSum);
        counts.put(currSum, counts.getOrDefault(currSum, 0) - 1); // 检查完当前分支就要减少当前前缀和的次数

        return res;
    }


}
